#pragma once
#include<assert.h>

namespace bit
{
	//节点类
	template<class T>
	struct ListNode
	{
		ListNode<T>* _next;//指向下一个节点的指针
		ListNode<T>* _prev;//指向上一个节点的指针
		T _data;//该节点的数据

		ListNode(const T& x = T())//构造函数
			:_next(nullptr)//置空
			, _prev(nullptr)//置空
			, _data(x)//x赋值
		{}
	};

	//迭代器类
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef ListNode<T> Node;//节点类的typedef
		typedef __list_iterator<T, Ref, Ptr> self;//返回值的typedef

		Node* _node;//唯一的一个成员变量(对内置类型封装成自定义类型)

		__list_iterator(Node* x)//构造函数 接收一个节点指针 赋值给成员变量
			:_node(x)
		{}

		// ++it
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		// it++
		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;

			return tmp;//返回的是tmp 但是*this本身已经++
		}

		//--it
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		//it--
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

		//*it
		Ref operator*()
		{
			return _node->_data;
		}

		//list类中的元素是一个自定义对象 
		Ptr operator->()
		{
			return &_node->_data;//返回的是该自定义对象的地址
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;//地址对比
		}

		bool operator==(const self& s)
		{
			return _node == s._node;//地址对比
		}
	};

	//链表类
	template<class T>
	class list
	{
		typedef ListNode<T> Node;//节点类的typedef
	public:
		typedef __list_iterator<T, T&, T*> iterator;//将迭代器类typedef为统一的名字
		typedef __list_iterator<T, const T&, const T*> const_iterator;//将迭代器类typedef为统一的名字
		//二者的不同在于list这个类的对象是否为const 


		iterator begin()
		{
			return _head->_next;//单参构造函数的隐式转换
		}

		iterator end()
		{
			return _head;//单参构造函数的隐式转换
		}

		const_iterator begin() const
		{
			return _head->_next;//单参构造函数的隐式转换
		}

		const_iterator end() const
		{
			return _head;//单参构造函数的隐式转换
		}

		void empty_init()//初始化一个链表
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			//创建一个头结点，自己指向自己
		}

		list()//构造函数复用初始化函数
		{
			empty_init();
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		~list()
		{
			clear();

			delete _head;
			_head = nullptr;
		}


		list(const list<T>& lt)//拷贝构造 被拷贝的对象不应该被修改
		{
			empty_init();//先对*this进行初始化

			for (const auto& e : lt)//从it中范围for边读取边push到*this中
			{
				push_back(e);
			}
		}

		void swap(list<T>& tmp)//交换函数 交换头结点即可
		{
			std::swap(_head, tmp._head);
		}

		//赋值函数
		list<T>& operator=(list<T> lt)//参数用传值 触发拷贝构造生成it
		{
			swap(lt);//再把it和*this交换 
			return *this;
		}

		//尾插
		void push_back(const T& x)
		{
			insert(end(), x);
		}

		//头插
		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		//尾删
		void pop_back()
		{
			erase(--end());
		}

		//头删
		void pop_front()
		{
			erase(begin());
		}

		// vector insert会导致迭代器失效
		// list会不会？不会  因为无扩容
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;//保存pos位置的节点
			Node* prev = cur->_prev;//保存pos位置的前一个节点
			Node* newnode = new Node(x);//用x创建一个新节点

			// prev newnode cur 缝合三者
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return newnode;//单参构造的隐式转换 这样也符合统一标准
		}

		//清理函数 只保留头结点
		iterator erase(iterator pos)
		{
			assert(pos != end());//end()为头结点 不能erase

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;//缝合

			delete cur;//释放

			return next;//返回pos位置的下一个节点
		}

	private:
		Node* _head;//list类的唯一一个成员变量 头结点
	};

}